package com.watson.onebox.algorithm;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class SortAlgorithm {

    public int[] bubbleSort(int[] arrays) {
        if (arrays.length <= 1) {
            return arrays;
        }

        for (int i = 0; i < arrays.length; i++) {
            for (int j = 0; j < arrays.length - 1 - i; j++) {
                if (arrays[j + 1] < arrays[j]) {
                    swap(arrays, j + 1, j);
                }
            }
        }
        return arrays;
    }

    /**
     * 冒泡排序优化
     */
    public int[] bubbleOptSort(int[] src) {

        int swapTime = 0, lastSwap, tmp = src.length - 1;
        for (int i = 0; i < src.length; i++) {
            lastSwap = tmp;
            for (int j = 0; j < lastSwap; j++) {
                if (src[j + 1] < src[j]) {
                    swapTime++;
                    tmp = j;
                    swap(src, j, j + 1);
                }
            }
            if (swapTime == 0) break;
            swapTime = 0;
        }

        return src;
    }

    public int[] selectSort(int[] arrays) {
        if (arrays.length <= 1) {
            return arrays;
        }
        for (int i = 0; i < arrays.length; i++) {
            int tmpPos = i;
            for (int j = i; j < arrays.length; j++) {
                if (arrays[j] < arrays[tmpPos]) {
                    tmpPos = j;
                }
            }
            swap(arrays, tmpPos, i);
        }
        return arrays;
    }

    //0 1 2 3 4 5 6 7 8 9
    public int[] insertSort(int[] arrays) {
        if (arrays.length <= 1) {
            return arrays;
        }

        for (int i = 0; i < arrays.length - 1; i++) {
            int tmp = arrays[i + 1];
            int curpos = i;
            while (curpos >= 0 && tmp < arrays[curpos]) {
                arrays[curpos + 1] = arrays[curpos];
                curpos--;
            }
            arrays[curpos + 1] = tmp;
        }

        return arrays;
    }

    /**
     * 选择排序优化
     */
    public int[] selectOptimize(int[] src) {
        int left = 0, right = src.length - 1;
        int minpos = 0, maxpos = 0;
        int j;
        while (left < right) {
            minpos = left;
            maxpos = left;
            for (j = left; j <= right; j++) {
                if (src[j] < src[minpos]) {
                    minpos = j;
                }
                if (src[j] > src[maxpos]) {
                    maxpos = j;
                }
            }
            swap(src, maxpos, right);

            if (minpos == right) {
                minpos = maxpos;
            }
            swap(src, minpos, left);
            left++;
            right--;
        }
        return src;
    }

    //希尔排序
    public int[] shellSort(int[] src) {
        if (src.length <= 1) {
            return src;
        }

        for (int d = src.length / 2; d > 0; d = d / 2) {
            for (int i = d; i < src.length; i++) {
                for (int j = i - d; j >= 0; j -= d) {
                    if (src[j] > src[j + d]) {
                        swap(src, j, j + d);
                    }
                }
            }
        }
        return src;
    }

    /**
     * 基数排序
     */
    public int[] radixSort(int[] sourceArray) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            //把桶里的数从0开始顺序放回arr中
            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

    //归并排序
    public void mergeSort1(int[] src, int low, int high) {
        if (low < high) {
            int mid = (high + low) / 2;
            mergeSort1(src, low, mid);
            mergeSort1(src, mid + 1, high);
            merge(src, low, mid, high);
        }
    }

    public void merge(int[] src, int low, int mid, int high) {

        int low1 = low;
        int high1 = mid + 1;
        int pos = 0;
        int[] tmp = new int[high - low + 1];
        while (low1 <= mid && high1 <= high) {
            if (src[low1] < src[high1]) {
                tmp[pos++] = src[low1++];
            } else {
                tmp[pos++] = src[high1++];
            }
        }

        while (low1 <= mid) tmp[pos++] = src[low1++];
        while (high1 <= high) tmp[pos++] = src[high1++];

        pos = 0;
        while (low <= high) {
            src[low++] = tmp[pos++];
        }
    }


    public void merge1(int[] src, int left, int right) {
        if(left < right) {
            int mid = (left + right) / 2;
            merge1(src, left, mid);
            merge1(src, mid + 1, right);
            mergeList(src, left, mid, right);
        }
    }

    public void mergeList(int[] src, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int pos = 0;

        int low = left;
        int high = mid + 1;

        while(low <= mid && high <= right) {
            if(src[low] < src[high]) {
                tmp[pos++] = src[low++];
            } else {
                tmp[pos++] = src[high++];
            }
        }
        while(low <= mid) tmp[pos++] = src[low++];
        while(high <= right) tmp[pos++] = src[high++];

        pos = 0;
        while(left <= right) {
            src[left++] = tmp[pos++];
        }
    }

    /*
     * 迭代实现归并排序
     * */
    public void mergeIteration(int[] src, int size) {
        int i, lmin, lmax, rmin, rmax;
        int[] tmp = new int[size];
        for (i = 1; i < size; i *= 2) {
            for (lmin = 0; lmin < size - i; lmin = rmax) {
                rmin = lmax = lmin + i;
                rmax = lmax + i;
                if (rmax > size) {
                    rmax = size;
                }
                int next = 0;
                while (lmin < lmax && rmin < rmax) {
                    if (src[lmin] < src[rmin]) {
                        tmp[next++] = src[lmin++];
                    } else {
                        tmp[next++] = src[rmin++];
                    }
                }

                while (lmin < lmax) {
                    src[--rmin] = src[--lmax];
                }
                while (next > 0) {
                    src[--rmin] = tmp[--next];
                }
            }
        }
    }

    /*
     * 快速排序
     * */
    public int[] fastSort(int[] arrays) {
        if (arrays.length < 2) {
            return arrays;
        }
        quickSort(arrays, 0, arrays.length - 1);

        return arrays;
    }

    private void quickSort(int[] arrays, int low, int high) {
        if (low >= high) {
            return;
        }
        int index = point(arrays, low, high);

        quickSort(arrays, low, index - 1);
        quickSort(arrays, index + 1, high);
    }

    private int point(int[] arrays, int low, int high) {
        int tmp = arrays[low];
        while (low < high) {
            //要从高位开始判断，从低位会出错
            while (low < high && arrays[high] >= tmp) {
                high--;
            }
            arrays[low] = arrays[high];
            while (low < high && arrays[low] <= tmp) {
                low++;
            }
            arrays[high] = arrays[low];
        }

        arrays[low] = tmp;
        return low;
    }

    /*
     * 堆排序
     * */
    public int[] heapSort(int[] arrays) {
        //循环遍历整个数组把最大值放在最后一个
        for (int i = 0; i < arrays.length; i++) {
            maxHeapSwap(arrays, arrays.length - i);
            swap(arrays, arrays.length - 1 - i, 0);
        }
        return arrays;
    }

    private void maxHeapSwap(int[] arrays, int size) {
        //必须从后往前找是因为先构建底层的子树一步一步往上构建成大顶堆，如果从前往后找就会导致在底层交换完
        // size/2-1是最后一个非叶子节点，在比较的时候只需要找非叶子节点就可以
        // 必须要等于0，因为0节点的左右节点是1，2，也需要判断大小
        for (int i = size / 2 - 1; i >= 0; i--) {
//        for (int i = 0; i < size - 1; i++) {
            //size就是整个数组剩下未排序的个数,跟这里的i没关系
            buildHeap(arrays, i, size);
        }
    }

    private void buildHeap(int[] arrays, int rootNodePos, int size) {
        //因为是从后往前找的所以当
        if (rootNodePos < size) {
            int left = 2 * rootNodePos + 1;
            int right = 2 * rootNodePos + 2;
            int max = rootNodePos;

            //如果在数组范围内并且左节点比root节点大就记录下来,left和right要区分好
            if (left < size && arrays[max] < arrays[left]) {
                max = left;
            }

            //如果在数组范围内并且右节点比root节点大就记录下来
            if (right < size && arrays[max] < arrays[right]) {
                max = right;
            }

            //如果root节点是最大的就结束递归，否则就把最大值交换到root节点,然后继续递归
            if (max != rootNodePos) {
                swap(arrays, max, rootNodePos);
                buildHeap(arrays, max, size);
            }
        }
    }

    private void swap(int[] src, int a, int b) {
        int tmp = src[a];
        src[a] = src[b];
        src[b] = tmp;
    }

    private void test(int[] nums, int target) {
        int p = 0, q = nums.length;
        while (p < q) {
            int tmp = nums[p] + nums[q];
            if(tmp == target) {
                return;
            } else if(tmp > target) {
                p++;
            } else if(tmp < target) {
                q--;
            }
        }
        String a = "1";
        int b = a.charAt(0) - 'a';

    }
}
